package com.shuang.greed12;

import java.util.Arrays;

public class FindMinArrowShots {
    //贪心：一个弓箭尽可能多的射爆重叠的气球
    public int findMinArrowShots(int[][] points) {

        //用于记录结果
        int count = 1; //1 <= points.length 至少要一个弓箭

        //对数组按照左边界进行排序 使其有重叠的气球一定是相邻的
        // 使用Integer内置比较方法，不会溢出
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));

        //从前向后 遍历排序过的points
        for (int i = 1; i < points.length; i++) {
            //判断当前位置的气球区间是否和上一个区间重叠
            if (points[i][0] > points[i - 1][1]) {
                //当前位置的左边界 大于前一个位置的右边界 这两个区间不重叠
                //不重叠 需要弓箭数加一
                count++;
            } else {
                //当前位置和前一个位置区间重叠情况
                //要更新这两个位置的区间右边界 要变成两个位置区间右边界小的那个 为了遍历到下次位置时判断是否与这两个区间接着重叠
                points[i][1] = Math.min(points[i][1], points[i - 1][1]);

            }
        }

        return count;
    }
}
